//一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有
//元素 随机打乱 。 
//
// 给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 
//任意 顺序返回。 
//
// 
//
// 示例 1： 
//
// 输入：changed = [1,3,4,2,6,8]
//输出：[1,3,4]
//解释：一个可能的 original 数组为 [1,3,4] :
//- 将 1 乘以 2 ，得到 1 * 2 = 2 。
//- 将 3 乘以 2 ，得到 3 * 2 = 6 。
//- 将 4 乘以 2 ，得到 4 * 2 = 8 。
//其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。
// 
//
// 示例 2： 
//
// 输入：changed = [6,3,0,1]
//输出：[]
//解释：changed 不是一个双倍数组。
// 
//
// 示例 3： 
//
// 输入：changed = [1]
//输出：[]
//解释：changed 不是一个双倍数组。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= changed.length <= 10⁵ 
// 0 <= changed[i] <= 10⁵ 
// 
//
// Related Topics 贪心 数组 哈希表 排序 👍 64 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class FindOriginalArrayFromDoubledArray {
    public static void main(String[] args) {
        Solution solution = new FindOriginalArrayFromDoubledArray().new Solution();
        System.out.println(
                Arrays.toString(solution.findOriginalArray(new int[]{0, 5})));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 1,2,3,4,6,8
         *
         * @param changed
         * @return
         */
        public int[] findOriginalArray(int[] changed) {
            int n = changed.length;
            if ((n & 1) == 1) return new int[0];
            Arrays.sort(changed);
            Map<Integer, Integer> map = new HashMap<>();
            //记录有多少个
            for (int i : changed) {
                map.put(i, map.getOrDefault(i, 0) + 1);
            }


            int[] res = new int[n / 2];
            int index = 0;
            for (int i : changed) {
                if (map.get(i) == 0) continue;
                map.put(i, map.get(i) - 1);
                if (map.getOrDefault(i * 2, 0) == 0) return new int[0];
                map.put(i * 2, map.get(i * 2) - 1);
                res[index++] = i;
                if (index >= n / 2) return res;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}